package cn.cxq.learning.single_linked_list;

/**
 * 牛客题霸-全部题目
 * 划分链表 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：20397
 * 本题知识点： 链表 双指针
 *  算法知识视频讲解
 * 题目描述
 * 给出一个链表和一个值 ，以 为参照将链表划分成两部分，使所有小于 的节点都位于大于或等于 的节点之前。
 * 两个部分之内的节点之间要保持的原始相对顺序。
 * 例如：
 * 给出 1\to 4 \to 3 \to 2 \to 5 \to 21→4→3→2→5→2 和 \ x = 3 x=3,
 * 返回 1\to 2 \to 2 \to 4 \to 3 \to 51→2→2→4→3→5.
 * 示例1
 * 输入
 * 复制
 * {1,4,3,2,5,2},3
 * 返回值
 * 复制
 * {1,2,2,4,3,5}
 * 说明：本题目包含复杂数据结构ListNode，点此查看相关信息
 *  关联企业
 * 小米
 *  关联职位
 * 研发
 */
public class Partition {

    // 想了一想最终还是使用两个指针一个构建小于x的链表，一个构建大于x的链表，最后将其串联起来
    // 也大可放心，这样做不需要额外开辟内存给链表的节点：
    public ListNode partition (ListNode head, int x) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode low = new ListNode(0);
        ListNode high = new ListNode(0);
        ListNode pl = low;
        ListNode ph = high;
        ListNode cur = head;

        while (cur != null) {
            if (cur.val < x) {
                pl.next = cur;
                pl = pl.next;
            } else {
                ph.next = cur;
                ph = ph.next;
            }
            cur = cur.next;
        }

        ph.next = null;
        pl.next = high.next;

        return low.next;
    }
}
